package com.lx.algorithm.recursion.class19;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-18 18:22:11
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-18     张李鑫                     1.0         1.0 Version
 */


/**
 * https://leetcode.com/problems/stickers-to-spell-word
 */
public class StickersToSpellWord {
    /**
     * 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
     * arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
     * 返回需要至少多少张贴纸可以完成这个任务。
     * 例子：str= "babac"，arr = {"ba","c","abcd"}
     * ba + ba + c  3  abcd + abcd 2  abcd+ba 2
     * 所以返回2
     */

    public static int minStickers1(String[] stickers, String target) {
        if (stickers == null || stickers.length == 0 || target == null || target.isEmpty()) {
            return -1;
        }
        int p1 = process(stickers, target);
        return p1 == Integer.MAX_VALUE ? -1 : p1;
    }


    private static int process(String[] stickers, String chars) {
        if (chars.isEmpty()) {
            return 0;
        }
        int sum = Integer.MAX_VALUE;
        for (int j = 0; j < stickers.length - 1; j++) {

            String minus = minus(chars.toCharArray(), stickers[j].toCharArray());
            if (minus.length() != chars.length()) {
                sum = process(stickers, minus);
            }
        }
        return sum + (sum == Integer.MIN_VALUE ? 0 : 1);
    }

    public static String minus(char[] target, char[] str) {
        int[] count = new int[26];
        for (char c : target) {
            count[c - 'a']++;
        }
        for (char c : str) {
            count[c - 'a']--;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0) {
                for (int j = 0; j < count[i]; j++) {
                    stringBuilder.append((char) (i + 'a'));
                }

            }
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        String[] arr = {"these", "guess", "about", "garden", "him"};
        String a = "atomher";
        System.out.println(minStickers1(arr, a));
    }

}
